package com.shiguiwu.springmybatis.algorithm.dyprogram;

/**
 * @description: 动态规划算法
 * 1、背包问题主要是指一个给定容量的背包、若干具有一定价值和重量的物品，如何选择物品放入背包使物品的价值最大。
 * 2、其中问题分两种，01背包 和 完全背包(完全背包指的是：每种物品都有无限件可用)
 * 3、这里的问题属于01背包，即每种类物品最多放一个。而无限背包可以转化为01背包。
 * 4、算法的主要思想，利用动态规划来解决。每次遍历到的第i个物品，根据 w[i] 和 v[i] 来确定是否需要将该物品放入背包中。v[i][j] 表示在前 i 个物品中能够装入容量为 j 的背包中的最大价值，公式和解释如下：
 * （1） w[i] 表示 第 i 个商品的重量， v[i] 表示 第 i 个商品的价值(价格) ，j 表示 当前背包的容量
 * （2） v[i][0] = v[0][j] =0; //表示 填入表 第一行和第一列是0
 * （3） 当w[i]> j 时：v[i][j] = v[i-1][j] ; // 当准备加入新增的商品的容量大于 当前背包的容量时，就直接使用上一个单元格的装入策略 (阿K解释：就是现在月薪很低的你买不起贵的，你只能买得起和上个月月薪一样的东西...)
 * （4） 当 j>=w[i] 时： v[i][j] = max{v[i-1][j], v[i]+v[i-1][j-w[i]]} ; // 当 准备加入的新增的商品的容量小于等于当前背包的容量（其中max 内的参数分两个 ，比较出最大的一个 ，赋值 给 v[i][j]）,具体解释：
 * v[i-1][ j ] ： 既上一个单元格的装入的最大值（已有的值）
 * v[ i - 1 ] [ j - w[ i ] ] ： 装入i-1商品，到剩余空间为 j-w[i] 的最大值
 * 注：此二位数组可以看成 x轴和 y 轴， v[y] [x] 或者 v[i] [j]，以后表格对应，x轴对应的是 重量(容量)，y轴则是 物品编号
 *
 * @author: stone
 * @date: Created by 2021/11/5 14:06
 * @version: 1.0.0
 * @pakeage: com.shiguiwu.springmybatis.algorithm.dyprogram
 */
public class DynamicProgramming {

    public static void main(String[] args) {

    }
}
